package com.dy.分类.链表.复制带随机指针的链表;
/*
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。



示例：



输入：
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

解释：
节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。


提示：

你必须返回给定头的拷贝作为对克隆列表的引用。
 */

import java.util.HashMap;

/**
 * 思路，第一次遍历，将克隆的节点放在原来节点后面
 * 第二次遍历，复制随机的节点
 * 方法二：
 * 用两个map，第一个映射 地址到序号
 * 第二个映射序号到映射
 */
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {
    }

    public Node(int _val, Node _next, Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
}

public class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        HashMap<Node, Integer> map1 = new HashMap<>();
        HashMap<Integer, Node> map2 = new HashMap<>();


        Node p = head;
        int i = 0;
        while (p != null) {
            map1.put(p, i);
            Node newNode = new Node();
            newNode.val = p.val;
            map2.put(i, newNode);
            p = p.next;
            i++;
        }
        p = head;
        i = 0;
        while (p != null) {
            Integer random = map1.get(p.random);
            Node current = map2.get(i);
            current.next = map2.get(i + 1);
            current.random = map2.get(random);
            p = p.next;
            i++;
        }
        return map2.get(0);

    }

    //如果被限制空间
    public Node copyRandomList2(Node head) {
        Node p = head;
        //第一次将新节点复制到原来节点后面
        while (p != null) {
            Node newNode = new Node();
            newNode.val = p.val;
            newNode.next = p.next;
            p.next = newNode;
            p = newNode.next;
        }
        //第二次赋值随机节点
        p = head;
        while (p != null) {
            p.next.random = p.random==null?null:p.random.next;
            p = p.next.next;
        }
        //第三部拆分两个链表
        p = head;
        Node newHead = new Node();
        Node q = newHead;
        while (p != null) {
            q.next = p.next;
            p.next = p.next.next;
            p=p.next;
            q=q.next;
        }
        return newHead.next;
    }
}
